package com.example.algorithms.sort;

/**
 * @Author Zhang Jie
 * @Date 9/28/20
 * @Version 1.0
 */

import java.util.Arrays;

/**
 * 堆排序
 * 堆是一个完全二叉树，使用数组存储，数组下标从1开始,子节点的位置为2i和2i+1
 * 堆中的每个节点的值都必须大于等于【大顶堆】（或小于等于【小顶堆】）其子节点的值。
 * 堆排序是一种原地的、时间复杂度为O(nlogn)且不稳定的排序算法。
 * 整个堆排序的实现分为建堆和排序两个步骤。
 *
 * 不是稳定的排序算法
 * 是原地排序算法
 *
 * 时间复杂度为O(nlogn)
 *
 *
 * TODO： 下面的代码和文章中的不一样，需要再看一下
 * @author jane
 */
public class HeapSort {

//建堆
    //第一种：往堆中插入一个元素，将待排序数组分成“堆区”和“待插入堆区”
    /**
     *第二种：将整个待排序数组当成一个“堆”，然后对其从后向前依次进行整体调整。只需要从第一个非叶子节点开始调整
     * 元素下标从1开始
     */
    private static void buildHeap(int[] arr){
        if(arr==null||arr.length<3){
            return;
        }
        int maxIndex=arr.length-1;
        //从最后一个非叶子节点开始调整
        for(int i=maxIndex/2;i>=1;i--){
            heapifyOneNode(arr,i);
        }
    }

    /**
     * 大顶堆,这个方法应该和下面heapifyFromTop合并为一个
     * @param arr
     * @param top
     */
    private static void heapifyOneNode(int[] arr, int top){
        int childIndex=2*top;
        int maxIndex=arr.length-1;
        if((2*top+1)<=maxIndex){
            childIndex = arr[2*top]>arr[2*top+1]?(2*top):(2*top+1);
        }
        if(arr[top]<arr[childIndex]){
            int temp=arr[top];
            arr[top]=arr[childIndex];
            arr[childIndex]=temp;
        }
    }

    /**
     * 从堆顶开始堆化,直到end,因为end之后是已经排好序的部分
     * @param arr
     * @param top
     */
    private static void heapifyFromTop(int[] arr, int top, int end){
        int i = top;
        while (i<=end/2){
            int childIndex=2*top;
            if((2*top+1)<end){
                childIndex=arr[2*top]<arr[2*top+1]?(2*top+1):(2*top);
            }
            if(arr[childIndex]>arr[i]){
                swap(arr,childIndex,i);
            }else{
                break;
            }
            i=childIndex;
        }
    }

    /**
     * 排序
     */
    private static void heapSort(int[] arr){
        int index=arr.length-1;
        while (index>1){
            swap(arr,index,1);
            index--;
            heapifyFromTop(arr,1, index);
        }
    }

    private static void swap(int[] arr, int index1, int index2){
        int temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }

    public static int[] sortUp(int[] arr){
        int length=arr.length;
        int[] arrCopy = new int[length+1];
        arrCopy[0]=0;
        System.arraycopy(arr,0,arrCopy,1,length);
        //堆化
        buildHeap(arrCopy);
        System.out.println(Arrays.toString(arrCopy));
        //排序
        heapSort(arrCopy);
        System.out.println(Arrays.toString(arrCopy));
        System.arraycopy(arrCopy,1,arr,0,length);
        return arr;
    }
}
